package day04;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// No.15 三数之和
// https://leetcode.cn/problems/3sum/
public class No15 {
    /**
     * 寻找数组中所有和为0的不重复三元组
     *
     * @param nums 输入的整数数组
     * @return 所有和为0的不重复三元组列表
     */
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums == null || nums.length < 3) return new ArrayList<>();
        // 对数组进行排序，为双指针法做准备
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        // 遍历第一个数的位置
        for (int first = 0; first < nums.length - 2; first++){
            // 跳过重复的第一个数，避免重复解
            if (first > 0 && nums[first] == nums[first - 1])
                continue;
            // 使用双指针法寻找另外两个数
            int second = first + 1;
            int third = nums.length - 1;
            while(second < third){
                int sum = nums[first] + nums[second] + nums[third];
                if(sum > 0){
                    // 和大于0，右指针左移
                    third--;
                } else if (sum < 0) {
                    // 和小于0，左指针右移
                    second++;
                }else {
                    // 找到和为0的三元组，添加到结果中
                    result.add(Arrays.asList(nums[first], nums[second], nums[third]));
                    // 跳过重复的数字，避免重复解
                    int temp = nums[third];
                    while(second < third && nums[third] == temp) third--;
                    temp = nums[second];
                    while(second < third && nums[second] == temp) second++;
                }
            }
        }
        return  result;
    }

}
